Businesses or households generally have a set of accounts payables. For example, a company may have a tax bill to pay on April 15, salary payments to be made on April 28, lease payments to be made on May 1, etc. Businesses or households also have a certain amount of cash available for making payments of the accounts payable for a given day. Often times, businesses or households are particularly interested in figuring out the best way to utilize the amount of cash available for a given day for making payments of the accounts payable. They have a limited amount of cash available to make such payments on a given day, and thus would like to know which of the accounts payables and what fraction of those accounts payables they should pay on that day to make the best use of their limited amount of cash available on that day. They would also like to make payments of an amount as close as possible to the amount of cash available for that day, since that amount is what was earmarked for accounts payables for that given day.
In general, accounts payables have an amount to pay, a due date, certain penalties incurred for late payment, minimum required payment, and the like. One or more of these elements of the accounts payable should be considered to decide which of the account payables and what fraction of the account payables should be paid. For example, businesses may decide to make a certain payment on a given day earlier than the due date if there are certain benefits associated with early payments, such as a discount of the payment amount. Businesses may also decide not to make a certain payment on a given day even though the payment is due on that day, notwithstanding the penalties associated with late payments, because the amount of cash available on that day is less than the amount of payment to be made for that account payable. Businesses also may prefer lumping more than one payment to a single payee (vendor) on a given day together to minimize delivery cost, or may also prefer separating the payments for ease of identification and accounting.
Therefore, business and households should, but typically do not, consider various factors (or objectives) in deciding when and how much of a payment should be made on a given day, such as, maximizing the amount of payments made on a given day within the limits of the amount of cash available for a given day, maximizing or minimizing payments to a certain vendor or a certain account depending upon the importance of the vendor or account, maximizing discounts, minimizing late fees, minimizing new late fees, favoring late payables, favoring aged payables, minimizing delivery costs, favoring the least recently paid account, maximizing partial payments, minimizing full payments, maximizing the number of payables paid, minimizing the total days late, minimizing the total days early, etc. A very efficient bill payment plan (a plan dictating which and how much of the payment obligations of the accounts payable should be satisfied on that day) taking into consideration all of these objectives in an optimized manner could result in savings of a significant amount of money for the businesses.
It is a very complicated task to find a solution for an efficient bill payment plan while optimizing these various factors. Consider, for example, a highly simplified situation where the accounts payable includes 100 different payment obligations of $100 due on 10 different dates on a given day. The search space for this situation would involve devising a bill payment plan to pay all or some part of each payment obligation on the given day while satisfying the above-mentioned factors objectives. Assuming that payments can be made in $1 increments between $0 and $100, just to simplify the calculation, there will be 100 ways to make a payment for each payment obligation. This means that there will be 100 ways to make payments on 100 payment obligations on the given day, resulting in 100100 combinations of possible solutions, clearly too many to be each individually considered even on the most powerful computers in existence. In addition, a variety of the above-mentioned objectives should be considered when finding the solution with respect to a user-specified importance level for each objective. The solution space for such a situation will be enormous, discontinuous in scope and will typically involve non-linear, non-dimensional, and inter-dependent variables.
Such a complicated problem is very difficult to solve, but once a solution is obtained, it is easy to evaluate the solution. Such problems are called non-deterministic polynomial (“NP”) problems, which mean that it is possible to guess the solution by some non-deterministic algorithm and then check the solution, both in polynomial time. Generally, NP problems may be solved by genetic algorithms. However, so far there has been no attempt to apply a genetic algorithm to finding a solution for optimizing a bill payment plan while optimizing certain objectives of a user.